#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* ptr_a = headA;
        ListNode* ptr_b = headB;
        while (ptr_a != ptr_b) {
            if (ptr_a == nullptr) {
                ptr_a = headB;
            } else {
                ptr_a = ptr_a->next;
            }
            if (ptr_b == nullptr) {
                ptr_b = headA;
            } else {
                ptr_b = ptr_b->next;
            }
        }
        return ptr_a;
    }
};

int main() {
    ListNode a1(4), a2(1), a3(8), a4(4), a5(5);
    ListNode b1(5), b2(0), b3(1);
    a1.next = &a2;
    a2.next = &a3;
    a3.next = &a4;
    a4.next = &a5;
    b1.next = &b2;
    b2.next = &b3;
    b3.next = &a3;
    Solution solution;
    ListNode* output = solution.getIntersectionNode(&a1, &b1);
    return 0;
}

